package main

import (
    "crypto/sha256"
    "fmt"
)

type MerkleTree struct {
    Leaves []string
    Layers [][][]byte
}

func NewMerkleTree(leaves []string) *MerkleTree {
    mt := &MerkleTree{Leaves: leaves}
    if len(leaves)%2!= 0 {
        leaves = append(leaves, leaves[len(leaves)-1])
    }
    layer := make([][]byte, len(leaves))
    for i, leaf := range leaves {
        hash := sha256.Sum256([]byte(leaf))
        layer[i] = hash[:]
    }
    mt.Layers = append(mt.Layers, layer)
    for len(layer) > 1 {
        if len(layer)%2!= 0 {
            layer = append(layer, layer[len(layer)-1])
        }
        nextLayer := make([][]byte, len(layer)/2)
        for i := 0; i < len(layer)/2; i++ {
            combined := append(layer[2*i], layer[2*i+1]...)
            hash := sha256.Sum256(combined)
            nextLayer[i] = hash[:]
        }
        layer = nextLayer
        mt.Layers = append(mt.Layers, layer)
    }
    return mt
}

func (mt *MerkleTree) Root() []byte {
    return mt.Layers[len(mt.Layers)-1][0]
}

func main() {
    leaves := []string{"data1", "data2", "data3", "data4"}
    merkleTree := NewMerkleTree(leaves)
    root := merkleTree.Root()
    fmt.Printf("Merkle Tree Root: %x\n", root)
}